#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
  public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        // the + 1 make when len % 2 == 1, left - right == 1
        // so result = std::max(nums1[i-1], nums2[j-1]);
        int half_len = (nums1.size() + nums2.size() + 1) / 2;
        int imax = nums1.size(), imin = 0;
        while (imax >= imin) {
            int i = (imax + imin) / 2;
            int j = half_len - i;  // half_len > nums1.size()
            if (j != 0 and i != nums1.size() and nums1[i] < nums2[j - 1]) {
                imin = i + 1;
            } else if (i != 0 and j != nums2.size() and nums1[i - 1] > nums2[j]) {
                imax = i - 1;
            } else {
                int max_left = 0;
                if (j == 0) {
                    max_left = nums1[i - 1];
                } else if (i == 0) {
                    max_left = nums2[j - 1];
                } else {
                    max_left = std::max(nums1[i - 1], nums2[j - 1]);
                }
                if ((nums1.size() + nums2.size()) % 2 == 1) return max_left;

                int min_right = 0;
                if (j == nums2.size()) {
                    min_right = nums1[i];
                } else if (i == nums1.size()) {
                    min_right = nums2[j];
                } else {
                    min_right = std::min(nums1[i], nums2[j]);
                }
                return (min_right + max_left) / 2.0;  // must 2.0
            }
        }
        return 0.0;
    }

    double findMedianSortedArrays_uncompleted(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() < nums2.size()) return findMedianSortedArrays(nums2, nums1);
        int high1 = nums1.size() - 1, high2 = nums2.size() - 1;
        int low1 = 0, low2 = 0;
        // when we know mid1, we can get mid2 by
        // mid2 = (nums1.size() + nums2.size()) / 2 - mid1
        // this way is much easier
        // an addition benefit is when len%2 == 1, right - left == 1
        int mid1 = (high1 + high2) / 2, mid2 = 0;
        while (high1 > mid1 and high2 > mid2) {
            // std::cout << mid1 << ", " << mid2 << std::endl;
            if (mid2 - 1 >= 0 and nums1[mid1] < nums2[mid2 - 1]) {
                int offset = std::min((high1 - mid1) / 2, (mid2 - low2) / 2);
                mid1 += offset;
                low1 = 2 * mid1 - high1;
                mid2 -= offset;
                high2 = 2 * mid2 - low2;
            } else if (mid1 - 1 >= 0 and nums2[mid2] < nums1[mid1 - 1]) {
                int offset = std::min((high2 - mid2) / 2, (mid1 - low1) / 2);
                mid2 += offset;
                low2 = 2 * mid2 - high2;
                mid1 -= offset;
                high1 = 2 * mid1 - low1;
            } else {
                break;
            }
        }
        if ((nums1.size() + nums2.size()) % 2 == 1) {
        }
        return (std::max(nums1[mid1 - 1], nums2[mid2 - 1]) + std::min(nums1[mid1], nums2[mid2])) / 2;
    }
};

int main() {
    std::vector<int> nums1{1, 2, 2, 3, 4, 5};
    std::vector<int> nums2{2, 3, 5, 6, 7, 8};
    Solution s;
    s.findMedianSortedArrays(nums1, nums2);
    return 0;
}
